1. Field of the Invention
The present invention relates to information encryption and decryption techniques for use in those fields such as information network, transportation, finance, medical treatment and distribution, and in particular, relates to a modular multiplication method and a calculating device for realizing information encryption and decryption.
2. Description of the Related Art
Following the development of the information communication technique, it has been taken seriously to ensure the security on an information network, e.g. prevent a fraudulent use or destruction of data. As a result, the information encryption and decryption techniques are now being used not only in the information communication field, but also in those familiar fields such as transportation, finance, medical treatment and distribution. Therefore, the encryption and decryption techniques of this type are required to process the high-level security at high speeds.
In the encryption and decryption techniques, “asymmetrical encryption algorithm” is excellent in quality. The asymmetrical encryption algorithm represents an encryption algorithm wherein an encryption key and a decryption key differ from each other, and it is not easy to calculate one of them from the other.
As typical asymmetrical encryption algorithms, there have been available, for example, RSA (named from initials of three creators) encryption, ElGamal encryption, Rabin encryption and Williams encryption of the type that uses a modular multiplication. Further, there have been available systems of “digital signature” employing those encryption algorithms, and there is now a movement to standardize them. Typical ones subjected to the standardization are an RSA signature method, ElGamal signature method, Schnorr signature method, DSA (Digital Signature Algorithm) signature method and the like. All of them are of the type that uses a modular multiplication of a long bit length. Therefore, for realizing those digital signature systems, it is indispensable to develop a calculating method and device that can complete the long bit-length modular multiplication in a short time.
The foregoing RSA encryption, ElGamal encryption, Rabin encryption and Williams encryption use as a basis a form of modular multiplication given by an expression “A×BmodN”. This expression represents deriving a remainder when A×B is divided by N. In the encryption (decryption), A represents a “plaintext” subjected to encryption (decryption), and B and N represent “keys” for encryption (decryption).
When executing encryption and decryption of information using the modular multiplication, decoding of each key can be made difficult by elongating bit lengths of A, B and N. On the other hand, if the bit lengths of A, B and N are elongated, a long time is required for processing the modular multiplication. Thus, it is an important problem how to process the modular multiplication with the long bit lengths of A, B and N at a high speed.
Montgomery has proposed a system for obtaining a solution of a remainder calculation (mod calculation) by carrying out multiplication and simple bit string processing. Prior art using this Montgomery technique is described in, for example, JP-A-11-212456, JP-A-2000-132376 and JP-A-2001-51832.
The modular multiplication algorithm according to the Montgomery technique uses a modulus N(N>1) of remainder and a base R that is relatively prime with the modulus N of remainder and is greater than N. And, it utilizes the fact that a calculation of X×R′modN from a dividend X can be performed only by carrying out a division by the base R.
In this case, each of N, N′, R, R′ and X is an integer, and the dividend X satisfies a relation of 0≦X<R×N. Further, R′ is an inverse number (inverse value) of the base R on the modulus N of remainder, and a relation of R×R′−N×N′=1(0≦R′<N, 0≦N′<R) is satisfied.
When using a power of 2 as the base R, the division by the base R can be replaced with a shift operation in a binary notation calculation. Therefore, the calculation of X→X×R′modN can be processed at a high speed using an electronic calculating device.
First, with respect to a relation of M, R and N,
          ⁢                                          M            ·            N                    =                                    (                                                                    (                                          X                      ⁢                                                                                          ⁢                      mod                      ⁢                                                                                          ⁢                      R                                        )                                    ·                                      N                    ′                                                  ⁢                mod                ⁢                                                                  ⁢                R                            )                        ·            N                                                                                        ⁢                      ≡                                          X                ·                N                ·                                  N                  ′                                            ⁢              mod              ⁢                                                          ⁢              R                                                                                                    ⁢                      ≡                                          X                ·                                  (                                                            R                      ·                                              R                        ′                                                              -                    1                                    )                                            ⁢              mod              ⁢                                                          ⁢              R                                                                                                    ⁢                      ≡                                                            X                  ·                  R                  ·                                      R                    ′                                                  ⁢                                                                  ⁢                mod                ⁢                                                                  ⁢                R                            -                              X                ⁢                                                                  ⁢                mod                ⁢                                                                  ⁢                R                                                                                                                  ⁢                      ≡                                          -                X                            ⁢                                                          ⁢              mod              ⁢                                                          ⁢              R                                          
From the foregoing result,
                              X          +                      M            ·            N                          ≡                  X          +                      (                                          -                X                            ⁢                                                          ⁢              mod              ⁢                                                          ⁢              R                        )                                                                            ⁢                  ≡                      0            ⁢                                                  ⁢            mod            ⁢                                                  ⁢            R                              
From this expression, it is proved that a remainder of the division of X+M·N by R is “0”, i.e. X+M·N is divisible by R.
An algorithm Y=REDC(X) of X→X×R′modN is realized as follows.                Y=REDC(X)        M=(XmodR)×N′modR        Y=(X+M·N)/R        If Y≧N then Y=Y−N                    Y<N then return Y                        
In one-time REDC calculation as noted above, a remainder XmodN is not obtained, but X×R′modN is obtained. In order to obtain the remainder XmodN, the REDC calculation is again carried out in the following manner using the product of REDC(X) and R2modN that has been previously obtained.
                                          REDC            ⁡                          (                                                REDC                  ⁡                                      (                    x                    )                                                  ×                                  (                                                            R                      2                                        ⁢                    mod                    ⁢                                                                                  ⁢                    N                                    )                                            )                                =                                    (                              X                ×                                  R                  ′                                ⁢                mod                ⁢                                                                  ⁢                N                            )                        ×                          (                                                R                  2                                ⁢                mod                ⁢                                                                  ⁢                N                            )                        ×                          R              ′                        ⁢            mod            ⁢                                                  ⁢            N                                                        =                      X            ×                          R              ′                        ×                          R              2                        ×                          R              ′                        ⁢            mod            ⁢                                                  ⁢            N                                                        =          Xmodn                      ⁢        
In this manner, the remainder XmodN can be obtained. Here, the Montgomery algorithm is extended to the modular multiplication “A×BmodN”. In the normal form of a modular multiplication f(x),f(x)=A×BmodNbut, in case of a remainder calculation f′(x) according to the Montgomery technique,f′(x)=A×B×R′modN
First, as “precalculation”, N′, RmodN and R2modN are calculated, wherein R represents a power of 2 slightly greater than the modulus N, R′ represents an inverse value of R in a modN calculation (i.e. R×R′modN=1), and N′ represents an inverse value of N in the Montgomery technique (i.e. R×R′−N×N′=1) and 0<N′<R.
Then, setting calculated R2modN as B,A×B×R′modNis calculated and set as A. Then,A×B×R′modNis further calculated and set as A. Through the foregoing procedure, A×BmodN is obtained.
As described above, according to the algorithm of the Montgomery technique, the modular multiplication can be executed without using the division by N.
However, there have been the following problems in the algorithm according to the conventional Montgomery technique. Specifically, since, as described above, “precalculation” is necessary for calculating N′, RmodN and R2modN from the N value, the number of times of multiply-add calculations is large and thus a long calculation time is required. For example, if a multiply-add unit is used as a hardware resource in the conventional Montgomery technique, the number of times of required calculations is as follows.
It is assumed that the number of “1” in N when expressed in binary notation is m. For calculating N′, m-time multiply-add calculations are necessary. For calculating RmodN, one-time subtraction of R−N is necessary. For calculating R2modN, approximately 30-time multiply-add calculations are necessary. Further, for calculating A×B×R′modN, 3-time multiply-add calculations are necessary.
From the foregoing, assuming that the N value has an n-bit length and “1” is assigned to all the bits (m=n), the total number of times of calculations required in the conventional Montgomery technique includes (n+33)-time multiply-add calculations and one-time subtraction.
Further, in the algorithm according to the conventional Montgomery technique, there are two input limitations, i.e. the N value is an odd number and the most significant bit of a designated bit length is “1”.
Moreover, it is impossible to carry out a modular multiplication exceeding the calculable maximum number of bits of a multiply-add unit that is used as hardware.